#include <iostream>
#include <cassert>

template <class K, class V>
struct AVLTreeNode
{
    AVLTreeNode<K, V> _left;
    AVLTreeNode<K, V> _right;
    AVLTreeNode<K, V> _parent;
    std::pair<K, V> _kv;
    int _bf; // 平衡因子banary factor

    AVLTreeNode(const pair<K, V> &kv) : _kv(kv), _bf(0), _left(nullptr), _right(nullptr), _parent(nullptr)
    {
    }
};

template <class K, class V>
class AVLTree
{
    typedef AVLTreeNode<K, V> Node;

public:
    bool Insert(const pair<K, V> &kv)
    {
        if (_root == nullptr)
        {
            _root = new Node(kv);
        }
        Node *cur = _root;
        Node *parent = nullptr;
        while (cur)
        {
            if (cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                std::cout << "该元素已经存在" << std::endl;
                return false;
            }
        }
        cur = new Node(kv);
        if (cur == parent->_left)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }

        while (parent)
        {
            if (cur == parent->_right)
            {
                parent->_bf++;
            }
            else
            {
                parent->_bf--;
            }
            if (parent->_bf == 0)
            {
                break;
            }
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                cur = parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 && cur->_bf == 1)
            {
                // 左旋 RotateL
            }
            else if (parent->_bf == -2 && cur->_bf == -1)
            {
                // 右旋 RotateR
            }
            else if (parent->_bf == 2 && cur->_bf == -1)
            {
                // 右 左双旋
            }
            else if (parent->_bf == -2 && cur->_bf == 1)
            {
                // 左 右双旋
            }
            else
            {
                assert(false);
            }
        }
    }

    void RotateL(Node *parent)
    {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
            subRL->_parent = parent;

        Node *ppNode = parent->_parent;

        subR->_left = parent;
        parent->_parent = subR;
        if (parent == _root)
        {
            subR = _root;
            subR->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
            {
                ppNode->_left = subR;
            }
            else
            {
                ppNode->_right = subR;
            }

            subR->_parent = ppNode;
        }
        // 更新平衡因子
        parent->_bf = 0;
        subR->_bf = 0;
    }

    void RotateR(Node *parent)
    {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;

        Node *ppNode = parent->_parent;

        subL->_right = parent;
        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subL;
            }
            else
            {
                ppNode->_right = subL;
            }
            subL->_parent = ppNode;
        }
        // 更新平衡因子
        parent->_bf = subL->_bf = 0;
    }

private:
    Node *_root;
};

int main()
{
    return 0;
}